package 公司真题.去哪网;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class _数组元素 {
    static int topK(int[] array, int k) {

        // 使用HashMap存储每个元素以及每个元素的出现次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            map.put(array[i], map.getOrDefault(array[i], 0) + 1);
        }

        // 使用优先级队列
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });

        // 将所有map中的元素放入pq中
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            pq.offer(entry);
        }

        if (k == 0 || k > pq.size()) throw new IllegalArgumentException();

        int res = 0;
        while (k != 0) {
            k--;
            res = pq.poll().getKey();
        }
        return res;
    }
}
